package 股票_状态机;

import org.junit.Test;

public class 买卖股票的最佳时机_任意次_自回溯_极重要{
    /**
     * 回溯 - 自a
     *
     * 回溯板子更新 **
     *
     * 0,0,0 空起 （少一轮main遍历 -> 减少bug）
     *
     *  i
     *  for sI
     *    sI+1 status
     *
     * 股票
     *  1 不动 / 买 / 卖
     *  2 不动时 要跟踪 远处 买/卖/- status
     *
     */
    int[] prices;
    public int maxProfit(int[] prices) {
        this.prices = prices;
        backTrack(0, 0,0); // 空起
        return maxProfit;
    }

    int maxProfit = Integer.MIN_VALUE;
    public void backTrack(int sI, int status, int curProfit){
        if(sI == prices.length){
            maxProfit = Math.max(maxProfit, curProfit);
            return;
        }

        for (int i = sI; i < prices.length; i++) {
            /**
             * 2021年7月11日：
             *      好像不对 -> 拿与不拿 -> 只需要 i+1 把？
             */
            //不动  [ 这里statu不能写死0 因为不操作时，要跟踪 远处的 买/卖/- 情况]
            backTrack(i+1, status, curProfit);
            //买 （未动 or 卖完 才能买）
            if(status == 2 || status == 0 ){
                backTrack(i+1, 1, curProfit - prices[sI]); // 这里是sI，不是i i+1
            }
            //卖 （只有 买完 才能卖）
            if(status == 1){
                backTrack(i+1, 2, curProfit + prices[sI]);
            }
        }
    }

    @Test
    public void test() {
        System.out.println("RES:" + maxProfit(new int[]{7,1,3}));
    }
}
